package com.cdream.basic.algorithm.leetcode.dp;

import java.util.Arrays;

/**
 * @author cdream
 * @date 6/8/21
 */
public class Question416 {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) {
            return false;
        }
        int weight = sum / 2;

        // 从背包中拿接近weight的最大重量

        int[] dp = new int[weight+1];
        dp[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = weight; j >= nums[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);
            }
        }
        return dp[weight] == weight;
    }
}
